#include <iostream>
using namespace std;

int bsearch(int A[], int x, int y, int v) {
    while (x < y) {
        int m = x + (y - x) / 2;
        if (A[m] == v) return m;
        else if (A[m] > v) y = m;
        else x = m + 1;
    }
    return -1;
}

int lower_bound(int A[], int x, int y, int v) {
    while (x < y) {
        int m = x + (y - x) / 2;
        if (A[m] >= v) y = m;
        else x = m + 1;
    }
    return x;
}

int upper_bound(int A[], int x, int y, int v) {
    while (x < y) {
        int m = x + (y - x) / 2;
        if (A[m] > v) y = m;
        else x = m + 1;
    }
    return x;
}

int main() {
    int A[] = {1,2,2,2,2,3,4,5,8,9,9,10};
    int n = sizeof(A) / sizeof(int);
    for (int i = 0; i < n; ++i) 
        cout << A[i] << ' ';
    cout << endl;
    cout << "loc of 2: " << bsearch(A, 0, n, 2) << endl;
    cout << "lower_bound of 2: "
         << lower_bound(A, 0, n, 2) << endl;
    cout << "upper_bound of 2: "
         << upper_bound(A, 0, n, 2) << endl;
}
